#include <iostream>

using namespace std;

struct TreeNode
{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode()
		:val(0)
		,left(nullptr)
		,right(nullptr)
	{}
	TreeNode(int x)
		:val(x)
		, left(nullptr)
		, right(nullptr)
	{}
	TreeNode(int x, TreeNode* left, TreeNode* right) 
		:val(x)
		,left(left)
		,right(right) 
	{}
};
class Solution
{
public:
	int ans = 0;
	int findtt(TreeNode* root)
	{
		dfs(root);
		return ans;
	}
	int dfs(TreeNode* node)
	{
		if (node == nullptr)
		{
			return 0;
		}

		int sumleft = dfs(node->left);
		int sumright = dfs(node->right);
		ans += abs(sumleft - sumright);

		return sumleft + sumright + node->val;
	}

};

int main()
{
	TreeNode* C = new TreeNode(3);
	TreeNode* D = new TreeNode(5);
	TreeNode* A = new TreeNode(2, C, D);
	TreeNode* B = new TreeNode(9);
	TreeNode* root = new TreeNode(4, A, B);
	TreeNode* E = new TreeNode(7);
	B->right = E;
	Solution xz;
	int n = xz.findtt(root);
	cout << n << endl;

	return 0;
}
